翻訳と辞書 Words near each other ・ "O" Is for Outlaw ・ "O"-Jung.Ban.Hap. ・ "Ode-to-Napoleon" hexachord ・ "Oh Yeah!" Live ・ "Our Contemporary" regional art exhibition (Leningrad, 1975) ・ "P" Is for Peril ・ "Pimpernel" Smith ・ "Polish death camp" controversy ・ "Pro knigi" ("About books") ・ "Prosopa" Greek Television Awards ・ "Pussy Cats" Starring the Walkmen ・ "Q" Is for Quarry ・ "R" Is for Ricochet ・ "R" The King (2016 film) ・ "Rags" Ragland ・ ! (album) ・ ! (disambiguation) ・ !! ・ !!! ・ !!! (album) ・ !!Destroy-Oh-Boy!! ・ !Action Pact! ・ !Arriba! La Pachanga ・ !Hero ・ !Hero (album) ・ !Kung language ・ !Oka Tokat ・ !PAUS3 ・ !T.O.O.H.! ・ !Women Art Revolution Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク probabilistic automaton ： ウィキペディア英語版 probabilistic automaton In mathematics and computer science, the probabilistic automaton (PA) is a generalization of the non-deterministic finite automaton; it includes the probability of a given transition into the transition function, turning it into a transition matrix or stochastic matrix. Thus, the probabilistic automaton generalizes the concept of a Markov chain or subshift of finite type. The languages recognized by probabilistic automata are called stochastic languages; these include the regular languages as a subset. The number of stochastic languages is uncountable. The concept was introduced by Michael O. Rabin in 1963;〔 〕 a certain special case is sometimes known as the Rabin automaton. In recent years, a variant has been formulated in terms of quantum probabilities, the quantum finite automaton. ==Definition== The probabilistic automaton may be defined as an extension of a non-deterministic finite automaton $(Q,\backslash Sigma,\backslash delta,q\_0,F)$, together with two probabilities: the probability $P$ of a particular state transition taking place, and with the initial state $q\_0$ replaced by a stochastic vector giving the probability of the automaton being in a given initial state. For the ordinary non-deterministic finite automaton, one has * a finite set of states $Q$ * a finite set of input symbols $\backslash Sigma$ * a transition function $\backslash delta:Q\backslash times\backslash Sigma\; \backslash to\; P(Q)$ * a set of states $F$ distinguished as ''accepting'' (or ''final'') ''states'' $F\backslash subset\; Q$. Here, $P(Q)$ denotes the power set of $Q$. By use of currying, the transition function $\backslash delta:Q\backslash times\backslash Sigma\; \backslash to\; P(Q)$ of a non-deterministic finite automaton can be written as a membership function :$\backslash delta:Q\backslash times\backslash Sigma\; \backslash times\; Q\backslash to\; \backslash$ so that $\backslash delta(q,a,q^\backslash prime)=1$ if $q^\backslash prime\backslash in\; \backslash delta(q,a)$ and $\backslash delta(q,a,q^\backslash prime)=0$ if $q^\backslash prime\backslash notin\; \backslash delta(q,a)$. The curried transition function can be understood to be a matrix with matrix entries :$\backslash left()\_=\backslash delta(q,a,q^\backslash prime)$ The matrix $\backslash theta\_a$ is then a square matrix, whose entries are zero or one, indicating whether a transition $q\backslash stackrel\; q^\backslash prime$ is allowed by the NFA. Such a transition matrix is always defined for a non-deterministic finite automaton. The probabilistic automaton replaces this matrix by a stochastic matrix $P$, so that the probability of a transition is given by :$\backslash left()\_$ A state change from some state to any state must occur with probability one, of course, and so one must have :$\backslash sum\_\backslash left()\_=1$ for all input letters $a$ and internal states $q$. The initial state of a probabilistic automaton is given by a row vector $v$, whose components add to unity: :$\backslash sum\_\backslash left()\_=1$ The transition matrix acts on the right, so that the state of the probabilistic automaton, after consuming the input string $abc$, would be :$v\; P\_a\; P\_b\; P\_c$ In particular, the state of a probabilistic automaton is always a stochastic vector, since the product of any two stochastic matrices is a stochastic matrix, and the product of a stochastic vector and a stochastic matrix is again a stochastic vector. This vector is sometimes called the distribution of states, emphasizing that it is a discrete probability distribution. Formally, the definition of a probabilistic automaton does not require the mechanics of the non-deterministic automaton, which may be dispensed with. Formally, a probabilistic automaton ''PA'' is defined as the tuple $(Q,\backslash Sigma,P,\; v,\; F)$. A Rabin automaton is one for which the initial distribution $v$ is a coordinate vector; that is, has zero for all but one entries, and the remaining entry being one. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「probabilistic automaton」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.